package leetcode.leetcode_2300;

import java.util.Arrays;

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int n = spells.length;
        int[] ans = new int[n];
        int m = potions.length;
        for (int i = 0; i < n; i++) {
            long target = (success + spells[i] - 1) / spells[i];
            if (target > potions[m - 1]) {
                ans[i] = 0;
            } else {
                ans[i] = m - lowerBound(potions, target);
            }
        }
        return ans;
    }

    // 找到第一个大于target的元素下标
    public int lowerBound(int[] arr, long target) {
        int m = arr.length;
        int left = 0, right = m-1;
        while(left< right){
            int mid = left + (right - left) / 2;
            if (arr[mid] >=target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}